class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k == 0)return 0;
        int n = nums.size(),ans = 0,left = 0,right = 0,sum = 1;
        for(;right < n;right++)
        {
            sum*= nums[right];
            while(right >= left &&sum >= k){
                sum /= nums[left];
                left++;
            }
            ans += (right - left + 1);
        }   
        return ans;
    }
};
class Solution {
public:
    int countKConstraintSubstrings(string s, int k) {
        if (k == 0)
            return 0;
        int n = s.size(), ans = 0, left = 0, right = 0, sum1 = 0, sum0 = 0;
        for (; right < n; right++) {
            if (s[right] == '1')
                sum1++;
            else
                sum0++;
            while (sum1 > k && sum0 > k) {
                if (s[left] == '1')
                    sum1--;
                else
                    sum0--;
                left++;
            }
            ans += (right - left + 1);
        }
        return ans;
    }
};
class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        int n = nums.size(), left = 0, right = 0;
        long long ans = 0,sum = 0;
        for (; right < n; right++) {
            sum += nums[right];
            while (sum * (right - left + 1) >= k) {
                sum -= nums[left];
                left++;
            }
            ans += (right - left + 1);
        }
        return ans;
    }
};
bool fun(unordered_map<int, int>& window, int mode) {
    if (window.size() == 1) {
        return true;
    } else if (window.size() == 2) {
        return window.contains(mode - 2) | window.contains(mode - 1) |
               window.contains(mode + 1) | window.contains(mode + 2);
    } else if (window.size() == 3) {
        return window.contains(mode + 1) & window.contains(mode + 2) |
               window.contains(mode + 1) & window.contains(mode - 1) |
               window.contains(mode - 1) & window.contains(mode - 2);
    } else {
        return false;
    }
}
class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        int n = nums.size(), left = 0, right = 0, mmax = 0, mmin = 0;
        long long sum = 0, ans = 0;
        unordered_map<int, int> window;
        for (; right < n; right++) {
            window[nums[right]]++;
            while (!fun(window, nums[right])) {
                window[nums[left]]--;
                if (window[nums[left]] == 0)
                    window.erase(nums[left]);
                left++;
            }
            ans += right - left + 1;
        }
        return ans;
    }
};
class Solution {
public:
    int medianOfUniquenessArray(vector<int>& nums) {
        int n = nums.size();
        long long size = ((long long)n * (n + 1) / 2 + 1) / 2;
        auto check = [&](int upper) {
            long long ans = 0;
            int left = 0, right = 0;
            unordered_map<int, int> mm;
            for (; right < n; right++) {
                mm[nums[right]]++;
                while (mm.size() > upper) {
                    if (--mm[nums[left]] == 0)
                        mm.erase(nums[left]);
                    left++;
                }
                ans += right - left + 1;
                if (ans  >= size)
                    return true;
            }
            return false;
        };
        int left = 0, right = n;
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            (check(mid) ? right : left) = mid;
        }
        return right;
    }
};
using ll = long long;
class Solution {
public:
    vector<long long> countKConstraintSubstrings(string s, int k,
                                                 vector<vector<int>>& queries) {
        int n = s.length();
        vector<int> right(n,n);
        vector<ll> sum(n + 1);
        int cnt[2]{}, l = 0;
        for (int r = 0; r < n; r++) {
            cnt[s[r] & 1]++;
            while (cnt[0] > k && cnt[1] > k) {
                cnt[s[l] & 1]--;
                right[l++] = r;
            }
            sum[r + 1] = sum[r] + r - l + 1;
        }
        vector<ll> ans(queries.size());
        for (int i = 0; i < queries.size(); i++) {
            int l = queries[i][0], r = queries[i][1];
            int j = min(right[l], r + 1);
            ans[i] = sum[r + 1] - sum[j] + (long long)(j - l) * (j - l + 1) / 2;
        }
        return ans;
    }
};
const int num = 1e9+7;
class Solution {
public:
    int beautifulBouquet(vector<int>& flowers, int cnt) {
        int n = flowers.size(),right = 0,left = 0,ans = 0;
        //unordered_map<int,int> window;
        vector<int> window(100005);
        for( ; right < n;right++){
            window[flowers[right]]++;
            while(window[flowers[right]] > cnt)
            {
                --window[flowers[left]];
                // if(--window[flowers[left]] == 0)
                //     window.erase(flowers[left]);
                left++;
            }
            ans  =  (ans + right - left + 1)%num;
        }
        return ans;
    }
};